package baseclass.e_tree;

import utils.TreeNode;
import utils.TreeUtil;

import java.util.LinkedList;
import java.util.Queue;


/**
 层次遍历一棵树。
    从头节点开始，入队。
    出队，打印出队节点，然后对节点进行左右孩子入队。循环该过程。
    因为队列是先进先出，就保证了先后遍历的顺序。
 */
public class Code08_LevelTraverse {
    public static void levelTraverse(TreeNode head){
        if(head == null)
            return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(head);
        while(!queue.isEmpty()){
            head = queue.poll();
            System.out.println(head.val+" ");
            if(head.left != null){
                queue.offer(head.left);
            }
            if(head.right != null){
                queue.offer(head.right);
            }
        }
    }



    public static void main(String[] args) {
        TreeNode head = new TreeNode(4);
        head.left = new TreeNode(2);
        head.right = new TreeNode(6);
        head.left.left = new TreeNode(1);
        head.left.right = new TreeNode(3);
        head.right.left = new TreeNode(5);
//        head.right.right = new TreeNode(5);

        TreeUtil.printTree(head);
        levelTraverse(head);

    }
}
